package algo.A04_快速排序和归并排序;

import util.ArrayUtil;

import java.util.Arrays;

/**
 * 给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。
 * 编写一个方法，将 B 合并入 A 并排序。初始化 A 和 B 的元素数量分别为 m 和 n。
 */
public class T07_合并有序数组_倒序比较法 {
    public static void main(String[] args) {
        int[] A = ArrayUtil.getRandomArr(30, 1, 100);
        int[] B = ArrayUtil.getRandomArr(10, 1, 100);
        Arrays.sort(A);
        Arrays.sort(B);
        for (int i = A.length - 1; i >= A.length / 2; i--) {
            A[i] = 0;
        }
        ArrayUtil.print(A);
        ArrayUtil.print(B);
        int[] result = solution(A, B);
        ArrayUtil.print(result);
    }

    /*
     * 倒序比较法
     * 思路：因为数组A和数组B都是从小到大有序排列的，所以先从两数组的末端元素倒序开始比较，确保A和B中较大的元素先被排在后面，时间复杂度为O(m+n)
     * 一开始使用三个指针，分别指向A的最后一个数，B的最后一个数和A的末尾
     */
    private static int[] solution(int[] A,int[] B){
        int pA = A.length / 2 - 1;//A数组指针
        int pB = B.length - 1;//B数组指针
        int current = pA + pB + 1;//填数字指针
        //从右向左扫描
        while (pA >= 0 && pB >= 0){
            if (A[pA] >= B[pB]){
                A[current--] = A[pA--];
            }else {
                A[current--] = B[pB--];
            }
        }
        //遍历完后如果A有剩下的就让他剩吧，仍然有序
        //如果B有剩下的，要把B剩下的继续放到A去
        while (pB >= 0){
            A[current--] = B[pB--];
        }
        return A;
    }
}
